//  全排列 1
// 方法 1
function backtrack(n, output, res, first) {
  if (first === n) {
    res.push(output)
  }
  for (let i = first; i < n; i++) {
    ;[output[first], output[i]] = [output[i], output[first]]
    backtrack(n, output.slice(), res, first + 1)
    ;[output[first], output[i]] = [output[i], output[first]]
  }
}
var permute = function (nums) {
  let res = []
  let output = []
  for (let num of nums) {
    output.push(num)
  }
  const n = nums.length

  backtrack(n, output, res, 0)
  return res
}
// 方法 2 逐步构建路径，记录是否使用，并做回退操作
var dfs = function (nums, res, path, used) {
  if (path.length === nums.length) {
    res.push(path)
    return
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue
    path.push(nums[i])
    used[i] = true
    dfs(nums, res, path.slice(), used)
    path.pop()
    used[i] = false
  }
}
var permute = function (nums) {
  let res = []
  let path = []
  let used = new Array(nums.length).fill(false)

  dfs(nums, res, path, used)

  return res
}
